package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//节点逐层替换:0ms 100%,3MB 9%
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	res, queue := [][]int{}, []*TreeNode{root}
	for i := 0; len(queue) > 0; i++ {
		res = append(res, []int{})
		tmp := []*TreeNode{}
		for _, v := range queue {
			if i%2 == 0 {
				res[i] = append(res[i], v.Val)
			} else {
				res[i] = append([]int{v.Val}, res[i]...)
			}
			if v.Left != nil {
				tmp = append(tmp, v.Left)
			}
			if v.Right != nil {
				tmp = append(tmp, v.Right)
			}
		}
		queue = tmp
	}
	return res
}

func main() {
	t := &TreeNode{1,
		&TreeNode{2, &TreeNode{4, nil, nil}, nil},
		&TreeNode{3, nil, &TreeNode{5, nil, nil}}}
	fmt.Println(levelOrder(t))
}
